package com.lry.basic.algorithm.common;

/**
 * @author:刘仁有
 * @desc:
 * 一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。
 * 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。
 * 问总共有多少条不同的路径？
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/unique-paths
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @email:953506233@qq.com
 * @data:2019/9/6
 */
public class UniquePaths {
    public static void main(String[] args) {
        System.out.println(uniquePaths(7, 3));
        System.out.println(minPathSum(new int[][]{{1,3,1},{1,5,1},{4,2,1}}));
        System.out.println(uniquePathsWithObstacles(new int[][]{{0,0,0},{0,1,0},{0,0,0}}));
    }

    public static int uniquePathsWithObstacles(int[][] obstacleGrid) {
        if(obstacleGrid[0][0]==1) return 0;
        obstacleGrid[0][0]=1;
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;
        //初始化dp第一行数据
        for(int i=1;i<m;i++){
            obstacleGrid[0][i] = (obstacleGrid[0][i]==0&&obstacleGrid[0][i-1]==1)?1:0;
        }
        //初始化dp第一列数据
        for(int i=1;i<n;i++){
            obstacleGrid[i][0] = (obstacleGrid[i][0]==0&&obstacleGrid[i-1][0]==1)?1:0;
        }
        //动态规划
        for(int i=1;i<m;i++){
            for(int j=1;j<n;j++){
                //是障碍物
                if(obstacleGrid[i][j]==1){
                    obstacleGrid[i][j] = 0;
                }else{
                    obstacleGrid[i][j] = obstacleGrid[i-1][j] + obstacleGrid[i][j-1];
                }
            }
        }
        return obstacleGrid[m-1][n-1];
    }

    public static int uniquePaths(int m, int n) {
        if(m<=0||n<=0)return 0;
        int[][] dp = new int[m][n];
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(i==0||j==0){
                    dp[i][j]=1;
                }else{
                    dp[i][j]=dp[i-1][j]+dp[i][j-1];
                }
            }
        }
        return dp[m-1][n-1];
    }
//            [1,3,1],
//            [1,5,1],
//            [4,2,1]
    public static  int minPathSum(int[][] grid) {
        if(null==grid||grid.length<1||grid[0].length<1)return -1;
        for(int i=0;i<grid.length;i++){
            for(int j=0;j<grid[0].length;j++){
                if(i==0){
                    if(j>0){
                        grid[i][j] = grid[i][j]+grid[i][j-1];
                    }
                }
                else if(j==0){
                    if(i>0){
                        grid[i][j] =  grid[i][j]+grid[i-1][j];
                    }
                }
                else
                grid[i][j]+=Math.min(grid[i-1][j],grid[i][j-1]);
            }
        }
        return grid[grid.length-1][grid[0].length-1];
    }
}
